The present invention relates to a system using a network similar to a discrimination network for judging whether or not conditions are satisfied, and in particular, to a method for modifying a discrimination network suitable for a knowledge base system.
As a method for judging at a high speed whether or not conditions are satisfied, there has been known a method in which a network similar to a discrimination network is used ("Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem"; Artificial Intelligence, Vol. 19, No. 1, 1982). In this method, conditions related to tokens or objects each comprising a token name and at least a pair of an attribute name and an attribute value are converted into a network, which is used to judge whether or not the conditions are satisfied.
A condition related to a token includes a plurality of condition clauses associated with the attribute of the token and the condition clause corresponds to a node of the network. For achieving the judgment, a token is passed through the network so as to determine whether or not the token satisfies the condition clause stored in each node. If this is the case, the token is passed to the next node, otherwise, the processing is stopped. This operation is repeated for all nodes. If the processing reaches the last node, it is judged that the condition of which the name is described in the node has been satisfied. This system therefore achieves the processing to judge the conditions at a high speed.
Generally, in a condition judge method using such a network, the efficiency of the network is higher when there exists a few tokens satisfying the conditions associated with the nodes, namely, nodes related with critical or severe conditions are placed at positions in the neighborhood of a root node of the network.
In practice, however, the writer of the conditions must obtain information about how the conditions are converted into a network to properly arrange the condition clauses in the conditions, for example, condition clauses which are not likely to be satisfied by the token are located at positions in the neighborhood of the root node of the network. This imposes a heavy burden on the writer of the conditions.
For the writer, on the other hand it is difficult to find out the ratio at which each condition clause is satisfied; moreover, since such a ratio at which each node is satisfied is dynamically changed when the characteristic of the objective phenomenon varies, the efficiency of the network operation according to the conventional method in which the writer arranges the condition clauses as described above is limited.
The first problem of the prior are method is that the condition clauses are arranged or ordered by the writer of conditions and that the order is assumed to be fixed.
In the condition judge system, if the node processing information is generated at an interval of a predetermined period to compare the obtained information with the previous information, the difference therebetween can be attained. In such a case, the network can be modified (for example, the order of nodes with respect to the levels relative to the root node is rearranged). Consequently, even if the characteristic of the objective problem is changed and the satisfaction ratios of the conditions stored in the nodes are varied, an efficient network can be established in any cases by dynamically modifying the network.
However, the rearrangement of the nodes in the network is accompanied by the following problems.
First, a ratio at which a node is satisfied or a satisfaction ratio of a node strongly depends on the relationships of the node with the higher-level and lower-level nodes. For example, assume that node A is at a higher level with respect to node B and that the satisfaction ratios of nodes A and B are 0.5 and 0.2, respectively. In this case, the ratio of 0.2 is a conditional probability, and hence the network processing efficiency cannot be necessarily increased even when the levels of the nodes A and B are exchanged.
Second, rearrangement of the nodes with respect to the hierarchic level in the network is essentially reduced to a problem of combination, which requires a great number of calculations.